// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// 包含整数数组的 minHeap 结构的定义
type minHeap struct {
	arr []int
}

// minHeap 结构的构造函数，它使用输入数组初始化 minHeap
func newMinHeap(arr []int) *minHeap {
	minHeap := &minHeap{
		arr: arr,
	}
	return minHeap
}

// 函数计算给定节点的左子节点在 minHeap 中的索引
func (m minHeap) leftChildIndex(index int) int {
	return 2*index + 1
}

// 计算给定节点在 minHeap 中的右孩子索引的函数
func (m minHeap) rightChildIndex(index int) int {
	return 2*index + 2
}

// 交换 minHeap 数组中的两个元素的函数
func (m *minHeap) swap(first, second int) {
	temp := m.arr[first]
	m.arr[first] = m.arr[second]
	m.arr[second] = temp
}

// 检查给定节点是否为 minHeap 中的叶节点的函数
func (m *minHeap) leaf(index int, size int) bool {
	if index >= (size/2) && index <= size {
		return true
	}
	return false
}

// 在 minHeap 中的给定节点上执行向下堆化的函数
func (m *minHeap) downHeapify(current int, size int) {
	// 如果当前节点是叶节点，则退出该函数
	if m.leaf(current, size) {
		return
	}
	// 初始设置当前节点为最小节点
	smallest := current
	// 计算当前节点的左孩子的索引
	leftChildIndex := m.leftChildIndex(current)
	// 计算当前节点的右孩子索引
	rightRightIndex := m.rightChildIndex(current)
	// 如果当前节点的左孩子小于当前节点，则将其设置为最小节点
	if leftChildIndex < size && m.arr[leftChildIndex] < m.arr[smallest] {
		smallest = leftChildIndex
	}
	// 如果当前节点的右孩子小于最小节点，则将其设置为最小节点
	if rightRightIndex < size && m.arr[rightRightIndex] < m.arr[smallest] {
		smallest = rightRightIndex
	}
	// 如果最小节点不是当前节点，交换两个节点，对最小节点进行向下堆化
	if smallest != current {
		m.swap(current, smallest)
		m.downHeapify(smallest, size)
	}
	return
}

// 通过对 minHeap 中的每个非叶节点执行向下堆化，从输入大小构建 minHeap 的函数
func (m *minHeap) buildMinHeap(size int) {
	// 循环遍历 minHeap 中的每个非叶节点并进行向下堆化
	for index := ((size / 2) - 1); index >= 0; index-- {
		m.downHeapify(index, size)
	}
}

// 函数对minHeap中的元素进行排序，构建一个minHeap，
// 将最小的元素反复交换到minHeap的末尾，对剩余的元素进行down-heapification。
func (m *minHeap) sort(size int) {
	// 构建最小堆
	m.buildMinHeap(size)
	// 从末尾循环遍历 minHeap 到第二个元素，
	// 将当前根与当前末尾元素交换，然后对剩余元素进行向下堆化
	for i := size - 1; i > 0; i-- {
		m.swap(0, i)
		m.downHeapify(0, i)
	}
}

// 打印 minHeap 中元素的函数
func (m *minHeap) print() {
	for _, val := range m.arr {
		fmt.Println(val)
	}
}

func main() {
	inputArray := []int{6, 88, 7, 33, 56, 58, 99, 3}
	minHeap := newMinHeap(inputArray)
	minHeap.sort(len(inputArray))
	minHeap.print()
}

//$ go run heapSort.go
//99
//88
//58
//56
//33
//7
//6
//3
